//
//  list_circle.hpp
//  cpp_algorithm
//
//  Created by 李贺 on 2021/12/2.
//

#ifndef list_circle_hpp
#define list_circle_hpp

#include <stdio.h>
#include <vector>
#include <iostream>
using namespace std;

class ListNode {
        
public:
    int val;
    ListNode *next;
    ListNode(int x): val(x),next(NULL){}
};

class Solution_list_circle {
public:
    ListNode *detectCycle(ListNode *head) {
            ListNode* fast = head;
            ListNode* slow = head;
            while(fast != NULL && fast->next != NULL) {
                slow = slow->next;
                fast = fast->next->next;
                // 快慢指针相遇，此时从head 和 相遇点，同时查找直至相遇
                if (slow == fast) {
                    ListNode* index1 = fast;
                    ListNode* index2 = head;
                    while (index1 != index2) {
                        index1 = index1->next;
                        index2 = index2->next;
                    }
                    return index2; // 返回环的入口
                }
            }
            return NULL;
        }
    
    void test() {
        ListNode * headA = new ListNode(88);
        
        ListNode * node1 = new ListNode(1);
        ListNode * node2 = new ListNode(2);
        ListNode * node3 = new ListNode(3);
        ListNode * node4 = new ListNode(4);
        ListNode * node5 = new ListNode(5);
        ListNode * node6 = new ListNode(6);
        
        headA->next = node1;
        node1->next = node2;
        node2->next = node3;
        node3->next = node4;
        node4->next = node5;
        node5->next = node6;
        node6->next = node2;
        
        ListNode *poNode = this->detectCycle(headA);
        cout << poNode->val << endl;
    }
};

#endif /* list_circle_hpp */
